package written_examination_questions;

public class Demo20251108 {
    // 反转字符串
    public void reverseString(char[] s) {
        int left = 0, right = s.length - 1;
        while (left < right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
            left++;
            right--;
        }
    }

    // 最小覆盖子串
    public String minWindow(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();

        int[] hash1 = new int[128]; // 统计字符串 t 中字符出现的频次
        int kinds = 0; // 记录字符串 t 中的字符的种类
        for (char ch : t) { // 将 t 中的字符加入哈希表
            if (hash1[ch] == 0) {
                kinds++;
            }
            hash1[ch]++;
        }

        int[] hash2 = new int[128]; // 统计窗口中字符出现的频次

        int minlen = Integer.MAX_VALUE, begin = -1;
        for (int left = 0, right = 0, count = 0; right < s.length; right++){
            char in = s[right];
            // 进窗口  维护count
            hash2[in]++;
            if (hash2[in] == hash1[in]) {
                count++;
            }
            // 判断
            while (kinds == count) {
                // 更新结果
                if (right - left + 1 < minlen) {
                    begin = left;
                    minlen = right - left + 1;
                }
                // 出窗口  维护count
                char out = s[left];
                left++;
                if (hash2[out] == hash1[out]) {
                    count--;
                }
                hash2[out]--;
            }
        }
        if (begin == -1) return new String();
        else return ss.substring(begin, begin + minlen);
    }
}
